package targetToOffer.sixthDay;

/**
 * @author Godc
 * @description
 */
public class MaxProfit {
}
class MaxProfitSolution {
    public int maxProfit(int[] prices) {
        // dp[i]表示前i天的最大利润
        // 转移方程:dp[i]=max(dp[i-1],price[i]-minPrice)，前i天的最大利润和当天的最大利润的最大值
        // 状态压缩，profit=max(profit,prices[i]−min(cost,prices[i])
        // 初始化:dp[0]=0
        if(prices.length == 0) return 0;
        int profit = 0,cost = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if(prices[i]<cost) cost = prices[i];
            profit = Math.max(profit,prices[i]-cost);
        }
        return profit;
    }
}
